package binarytreedemo;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 黎鹤舞
 * Date: 2024-01-23
 * Time: 16:32
 */

//这里是通过固定输入来生成一个二叉树:
public class BinaryTree {

    /**
     * 通过内部类 实现二叉树的结点
     * 孩子表示法
     */
    static class TreeNode {
        public char val;
        public BinaryTree.TreeNode left;
        public BinaryTree.TreeNode right;

        public TreeNode (char val) {
            this.val = val;
        }
    }

    /**
     * 以穷举的方式生成二叉树
     */
    public TreeNode createTree () {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }

    //前序遍历: 根 左 右
    public void preOrder(TreeNode root) {
        if(root == null) {
            return; //空树无须遍历
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    //中序遍历 左 根 右
    public void inOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }


    //后序遍历:左 右 中
    public void postOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    //通过递归实现二叉树求结点个数
    public int size(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return size(root.left) + size(root.right) + 1;
    }

    /**
     * 获取二叉树的叶子结点个数
     * 方法一:
     * 遍历法
     * @param root
     */

    public int leafCount;
    public void getLeafNodeCount1(TreeNode root) {
        if(root == null) {
            return;
        }
        if(root.left == null && root.right == null) {
            leafCount++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }

    /**
     * 获取二叉树的叶子结点个数
     * 方法二:
     * 子问题法
     * @param root
     */
    public int getLeafNodeCount2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);

    }

    /**
     * 求二叉树第K层的结点个数
     */
    public int getKLevelNodeCount(TreeNode root,int k) {
        if(root == null) {
            return 0;
        }
        if(k == 1) {
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1) + getKLevelNodeCount(root.right,k-1);
    }

    /**
     * 求二叉树高度
     */
    public int getHeight(TreeNode root){
        if(root == null) {
            return 0;
        }

        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return leftHeight > rightHeight ? (leftHeight + 1) : (rightHeight + 1);
        //出现了重复计算
//        return getHeight(root.left) > getHeight(root.right) ?
//                (getHeight(root.left) + 1) : (getHeight(root.right) + 1);
    }

    //二叉树查找特定值
    public TreeNode find(TreeNode root, char val) {
        if(root == null) {
            return null;
        }

        if(root.val == val) {
            return root;
        }

        //把遍历条件看出
        TreeNode leftFind = find(root.left,val);
        if(leftFind != null) {
            return leftFind;
        }

        TreeNode rightFind = find(root.right,val);
        if(rightFind != null) {
            return rightFind;
        }
        return null;
        //错误代码:相当于遍历 但是结果是return null， 就算找到了了结点也会返回到第一个函数，最后return null
//        if(root.val == val) {
//            return root;
//        }
//        find(root.left,val);
//        find(root.right,val);
//        return null;
    }

    /**\
     * 二叉树的层序遍历
     */
    public void levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null) {
            return;
        }
        //入根节点
        queue.offer(root);
        //当队列中仍有元素时
        while(!queue.isEmpty()) {
            //打印并出队
            root = queue.poll();
            System.out.print(root.val + " ");
            if(root.left != null) {
                queue.offer(root.left);
            }
            if(root.left != null) {
                queue.offer(root.right);
            }
        }
    }

    public boolean completeTree(TreeNode root) {
        if(root == null) {
            return true;
        }
        //需要建立一个
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(queue.peek() != null) {
            TreeNode temp = queue.poll();
            if(temp != null) {
                queue.offer(temp.left);
                queue.offer(temp.right);
            }else {
                break;//如果该节点为null，就不在存放null的左右子树，防止空指针异常
            }

//            queue.offer(temp.left);
//            queue.offer(temp.right);
        }
        //此时栈顶元素为null
        while (!queue.isEmpty()) {
            queue.poll();
            if(queue.peek() != null) {
                return false;
            }
        }
        return true;
    }

}
